package com.sheng.leetcode.year2023.month01.day28;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/01/30
 * <p>
 * 1664. 生成平衡数组的方案数<p>
 * <p>
 * 给你一个整数数组 nums 。你需要选择 恰好 一个下标（下标从 0 开始）并删除对应的元素。请注意剩下元素的下标可能会因为删除操作而发生改变。<p>
 * 比方说，如果 nums = [6,1,7,4,1] ，那么：<p>
 * 选择删除下标 1 ，剩下的数组为 nums = [6,7,4,1] 。<p>
 * 选择删除下标 2 ，剩下的数组为 nums = [6,1,4,1] 。<p>
 * 选择删除下标 4 ，剩下的数组为 nums = [6,1,7,4] 。<p>
 * 如果一个数组满足奇数下标元素的和与偶数下标元素的和相等，该数组就是一个 平衡数组 。<p>
 * 请你返回删除操作后，剩下的数组 nums 是 平衡数组 的 方案数 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums = [2,1,6,4]<p>
 * 输出：1<p>
 * 解释：<p>
 * 删除下标 0 ：[1,6,4] -> 偶数元素下标为：1 + 4 = 5 。奇数元素下标为：6 。不平衡。<p>
 * 删除下标 1 ：[2,6,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：6 。平衡。<p>
 * 删除下标 2 ：[2,1,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：1 。不平衡。<p>
 * 删除下标 3 ：[2,1,6] -> 偶数元素下标为：2 + 6 = 8 。奇数元素下标为：1 。不平衡。<p>
 * 只有一种让剩余数组成为平衡数组的方案。<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums = [1,1,1]<p>
 * 输出：3<p>
 * 解释：你可以删除任意元素，剩余数组都是平衡数组。<p>
 * <p>
 * 示例 3：<p>
 * 输入：nums = [1,2,3]<p>
 * 输出：0<p>
 * 解释：不管删除哪个元素，剩下数组都不是平衡数组。<p>
 * <p>
 * 提示：<p>
 * 1 <= nums.length <= 10^5<p>
 * 1 <= nums[i] <= 10^4<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/ways-to-make-a-fair-array">1664. 生成平衡数组的方案数</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1664 {

    @Test
    public void test01() {
//        int[] nums = {2, 1, 6, 4};
//        int[] nums = {1, 1, 1};
        int[] nums = {1, 2, 3};
        System.out.println(new Solution().waysToMakeFair(nums));
    }

}

// 暴力破解，超时
//class Solution {
//    public int waysToMakeFair(int[] nums) {
//        int count = 0;
//        int length = nums.length;
//        for (int i = 0; i < length; i++) {
//            // 删掉第 i 个元素
//            int odd = 0;
//            int even = 0;
//            for (int j = 0; j < length; j++) {
//                if (j < i) {
//                    if (j % 2 == 0) {
//                        even += nums[j];
//                    } else {
//                        odd += nums[j];
//                    }
//                } else if (j > i) {
//                    int num = j - 1;
//                    if (num % 2 == 0) {
//                        even += nums[j];
//                    } else {
//                        odd += nums[j];
//                    }
//                }
//            }
//            if (odd == even) {
//                count++;
//            }
//        }
//        return count;
//    }
//}

//思路：计算数组中删除一个下标后，新数组的奇偶下标和相等的删除下标个数
//* 1. 先求出原数组奇偶下标和 记作 evenNum 和 oddNum。
//* 2. 当删除某个下标后，新的偶数和 = 这个下标左边的偶数和 + 这个下标右边的奇数和
//* 3. 当删除某个下标后，新的奇数和 = 这个下标左边的奇数数和 + 这个下标右边的偶数数和
//* 4. 新生成两个 变量 leftEvenNum leftOddNum 分别代表左边偶数和（不包含删除的元素） 、左边的奇数和（不包含删除的元素）
//* 5. 这样第二步的方程就等于 当 删除的元素是偶数时 偶数和 = leftEvenNum + (oddNum - leftOddNum) 奇数和 = evenNum - leftEvenNum - nums[i] + leftOddNum
//* 5. 这样第二步的方程就等于 当 删除的元素是奇数时 偶数和 = leftEvenNum + (oddNum - leftOddNum)- nums[i] 奇数和 = evenNum - leftEvenNum + leftOddNum
//* 循环nums 就能算出来 原数组有多少个了
//
class Solution {
    public int waysToMakeFair(int[] nums) {
        // 偶数
        int evenNum = 0;
        // 奇数
        int oddNum = 0;

        int leftEvenNum = 0;
        int leftOddNum = 0;

        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) {
                evenNum += nums[i];
            } else {
                oddNum += nums[i];
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) {
                // 代表是去除掉的偶数
                // 计算奇数
                if (evenNum - nums[i] + leftOddNum - leftEvenNum == oddNum + leftEvenNum - leftOddNum) {
                    sum++;
                }
                leftEvenNum += nums[i];
            } else {
                if (evenNum - leftEvenNum + leftOddNum == oddNum - nums[i] + leftEvenNum - leftOddNum) {
                    sum++;
                }
                leftOddNum += nums[i];
            }
        }
        return sum;
    }
}
//
//作者：xiao-bai-bu-hen-bai
//链接：https://leetcode.cn/problems/ways-to-make-a-fair-array/solution/by-xiao-bai-bu-hen-bai-5avb/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
